#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: func.py 
@version:
@time: 2024/01/23

1. "("与")"配对才能成为一对有效的括号
2. 无论如何组合，第一个符合一定是"("，这是可以固定的一个位置
3. 在确定当前位置是否可以添加")"时，需要考虑在此位置之前一共有多少个"("和")"。当左括号的数量小于或等于右括号的数量时，是不可能在当前位置添加")"的。
4. 在确定当前位置是否可以添加"("时，只要确定当前位置之前出现过"(“数量小于给定的k即可。

基于以上4点，可见在确定目前位置之前，需要知道到目前为止已经出现的各种括号的个数，
用left_num和right_num分别表示目前左括号的个数和右括号的个数。由于最终返回的结果是列表，
列表中需要包含各种组合方式，因此括号组合过程中需要通过一个字符串去累计目前组合方式，当所有给定符号都被放置完毕之后，就将字符串加入结果列表中。


递归终止条件就是当left_num与right_num之和等于给定符号的个数时，即回溯。否则，继续
向下深入，分为两种情况来判断；

一种是当前位置是否可以放置"("，只要目前为止左括号的个数小于给定k，即可放置；

第二种情况是判断当前位置是否可以放置")"，只要目前为止的right_num小于left_num即可。


"""


def func(k):
    re = []

    def dfs(left_num, right_num, string):
        if left_num + right_num == 2 * k:
            re.append(string)
            return
        if left_num < k:
            dfs(left_num + 1, right_num, string + "(")
        if right_num < left_num:
            dfs(left_num, right_num + 1, string + ")")

    dfs(1, 0, '(')
    return re


print(func(2))
